package Offer.offer2016;

//���Ϊ����ָ��start��end������start��ʼ�ߣ���ָ��Ϊ�ո���start��end
//����ǰ�ƶ�����startָ��Ĳ�Ϊ�ո���start������end������ʼ��ǰ�ߣ���
//endָ��ո�󣬴�ʱ���start��end-1��һ���ַ�����Ȼ��start��endͬʱ��
//����end+1��λ�ã��ظ�֮ǰ�жϹ��̡���end�ƶ������ѭ����ֹ��
public class Test42 
{

	public static void main(String[] args) 
	{
		String str="student. a am I";
		reverseSentence(str);
		ReverseStr.reverse(str);
	}
    public static void reverseSentence(String str)
    {
    	if(str==null)
    		return;
    	char[] ch=str.toCharArray();
        reverse(ch,0,ch.length-1);
        int start=0;
        int end=0;
        while(true)
        {
        	if(ch[start]==' ')
        	{
        		start++;
        		end++;
        	}
        	else if(ch[end]==' ')
        	{
        		reverse(ch,start,end-1);
        		start=++end;
        	}
        	else if(end==ch.length-1)
        	{
        		reverse(ch,start,end);
        		break;
        	}
        	else
        	{
        		end++;
        	}
        }
        for(int i=0;i<ch.length;i++)
        {
        	System.out.print(ch[i]);
        	
        }
        
    }
    public static void reverse(char[] ch,int start,int end)
    {
    	if(start==end)
    		return;
    	while(start<end)
    	{
    		char temp = ch[start];
    		ch[start]=ch[end];
    		ch[end]=temp;
    		start++;
    		end--;
    	}
    }
}

class ReverseStr{
	public static void reverse(String str){
		if(str==null || str.length() <= 0)
    		return;
		char [] ch = str.toCharArray();
		int length = ch.length;
		reverse(ch,0,length - 1);
		int start = 0;
		int end = 0;
		while(true){
			if(ch[start] == ' '){
				start ++;
				end ++;
			}else if(ch[end] == ' '){
				reverse(ch,start,end - 1);
				start = ++end;
			}else if(end == ch.length - 1){
				reverse(ch,start,end);
				break;
			}else {
				end ++;
			}
		}
		System.out.print(String.valueOf(ch));
	}
	public static void reverse(char []ch,int start,int end){
		if (start == end) {
			return;
		}
		while (start < end) {
			char tmp = ch[start];
			ch[start] = ch[end];
			ch[end] = tmp;
			start ++;
			end --;
		}
	}
}
